Dekompozycja acykliczna

Limit pamięci: 32 MB

Bajtazar zajmuje się grafami skierowanymi. Szczególnie upodobał sobie grafy bez cykli, bo jest to klasa grafów, w której wiele problemów posiada proste i efektywne rozwiązania. W tej chwili pracuje nad sposobem przedstawienia dowolnego grafu skierowanego jako sumy grafów acyklicznych.

Dla danego grafu skierowanego próbuje znaleźć sposób podziału jego zbioru krawędzi na minimalną liczbę podzbiorów, tak aby grafy złożone z krawędzi z każdego podzbioru nie posiadały cykli. Czy mógłbyś napisać program, który rozwiąże Bajtazarowi ten problem?

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (), oznaczające odpowiednio liczby wierzchołków oraz krawędzi w grafie. Wierzchołki są ponumerowane od do . Każdy z kolejnych wierszy zawiera opis jednej krawędzi w grafie w postaci pary liczb całkowitych , (). Taka para oznacza, że w grafie istnieje skierowana krawędź z wierzchołka do wierzchołka . Możesz założyć, że w grafie nie ma krawędzi wielokrotnych.

Wyjście

W pierwszym wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą - minimalną liczbę grafów acyklicznych, na które można rozłożyć graf. Każdy z kolejnych wierszy powinien zawierać opis jednego elementu rozkładu, rozpoczynający się od liczby całkowitej oznaczającej liczbę krawędzi w tym elemencie. Po niej powinien następować rosnący ciąg numerów krawędzi wchodzących w skład opisywanego elementu rozkładu. Krawędzie numerujemy od do , zgodnie z kolejnością na wejściu. Każda krawędź powinna wystąpić w dokładnie jednym elemencie rozkładu grafu.

Jeśli istnieje więcej niż jedno poprawne rozwiązanie, Twój program może wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

6 5
1 2
2 3
3 1
4 5
5 4

poprawną odpowiedzią jest:

2
2 3 5
3 1 2 4

Ilustracja przykładu z treści zadania. Kółka reprezentują wierzchołki, a linie i łuki (ciągłe i przerywane) krawędzie grafu. Liczby przy kółkach to numery wierzchołków, a liczby przy liniach/łukach to numery krawędzi. Ten graf można rozłożyć na dwa grafy acykliczne: krawędzie pierwszego z nich oznaczono liniami/łukami ciągłymi, a drugiego - liniami/łukami przerywanymi.

Autor zadania: Jakub Łącki.